/*
 * @lc app=leetcode id=115 lang=cpp
 *
 * [115] Distinct Subsequences
 */
class Solution {
public:
    int numDistinct(string s, string t) {
        int slen = s.size();
        int tlen = t.size();

        if (slen < tlen) {
            return 0;
        }

        vector<vector<long>> memo(slen+1, vector<long>(tlen+1, 0));
        for (int i=0; i<=slen; i++) {
            memo[i][0] = 1;
        }

        for (int i=1; i<=slen; i++) {
            for (int j=1; j<=tlen; j++) {
                if (s[i-1] == t[j-1]) {
                    memo[i][j] = memo[i-1][j-1] + memo[i-1][j]; 
                } else {
                    memo[i][j] = memo[i-1][j];
                }
            }
        }
        return memo[slen][tlen];
    }
};

